package com.congee02.spring.util;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;

/**
 * {@link ConcurrentHashMap} 对 {@code keys} 和 {@code values} 使用 
 * {@link ReferenceType#SOFT soft} 或 {@linkplain ReferenceType#WEAK weak} 引用
 * 
 * <p>此类可以用作 {@code Collections.synchronizedMap(new WeakHashMap<K, Reference<V>>())} 的替代方法，以便在并发访问时支持更好的性能。
 * 此实现遵循与 {@link ConcurrentHashMap} 相同的设计约束，但支持 {@code null} 值和 {@code null} 键。
 * 
 * <p><b>注意：<b>引用的使用意味着不能保证放置在地图中的项目随后可用。
 * 垃圾收集器可能会随时丢弃引用，因此可能会出现未知线程正在静默删除条目的情况。
 * 
 * <p>如果未明确指定，此实现将使用 {@linkplain SoftReference 软条目引用}
 * 
 * @author congee(congee02 @ 163.com)
 * @date 1/28/2023 4:54 PM
 */
public class ConcurrentReferenceHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {

    /**
     * 默认初始化容量
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 默认加载因子。设加载因子为 f，容量为 c，则容器中有 c * f 个元素时，扩容
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75F;


    /**
     * 默认的并发等级。并发等级:允许同时使用容器的最大线程数量
     */
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    /**
     * 默认为软引用
     */
    private static final ReferenceType DEFAULT_REFERENCE_TYPE = ReferenceType.SOFT;

    private static final int MAXIMUM_CONCURRENCY_LEVEL = 1 << 16;
    
    private static final int MAXIMUM_SEGMENT_SIZE = 1 << 30;
    
    private final Segment[] segments;

    /**
     * 当每个表的平均引用数超过此值时，将尝试调整大小
     */
    private final float loadFactor;

    /**
     * 引用类型：SOFT 或 WEAK。
     */
    private final ReferenceType referenceType;

    /**
     * 用于计算段数组大小的移位值和哈希的索引。
     */
    private final int shift;

    /**
     * 后期绑定条目集
     */
    private volatile Set<Map.Entry<K, V>> entrySet;
    
    /* CONSTRUCTORS */


    /**
     * 创建一个新的 {@code ConcurrentReferenceHashMap} 实例
     */
    public ConcurrentReferenceHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE);
    }

    /**
     * 创建一个新的 {@code ConcurrentReferenceHashMap} 实例
     * @param initialCapacity Map 初始容量
     */
    public ConcurrentReferenceHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE);
    }

    /**
     * 创建一个新的 {@code ConcurrentReferenceHashMap} 实例
     * @param initialCapacity Map 初始容量
     * @param loadFactor 负载系数。当每个表的平均引用数超过此值时，将尝试调整大小
     */
    public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL, DEFAULT_REFERENCE_TYPE);
    }

    /**
     * 创建一个新的 {@code ConcurrentReferenceHashMap} 实例
     * @param initialCapacity Map初始容量
     * @param concurrencyLevel 将同时写入映射的预期线程数
     */
    public ConcurrentReferenceHashMap(int initialCapacity, int concurrencyLevel) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR, concurrencyLevel, DEFAULT_REFERENCE_TYPE);
    }

    /**
     * 创建一个新的 {@code ConcurrentReferenceHashMap} 实例
     * @param initialCapacity Map初始容量 
     * @param referenceType 用于条目的引用类型（SOFT或WEAK）
     */
    public ConcurrentReferenceHashMap(int initialCapacity, ReferenceType referenceType) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL, referenceType);
    }

    /**
     * 创建一个新的 {@code ConcurrentReferenceHashMap} 实例
     * @param initialCapacity Map初始容量 
     * @param loadFactor 负载系数。当每个表的平均引用数超过此值时，将尝试调整大小
     * @param concurrencyLevel 将同时写入映射的预期线程数
     */
    public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
        this(initialCapacity, loadFactor, concurrencyLevel, DEFAULT_REFERENCE_TYPE);
    }

    /**
     * 创建一个新的 {@code ConcurrentReferenceHashMap} 实例
     * @param initialCapacity Map初始容量 
     * @param loadFactor 负载系数。当每个表的平均引用数超过此值时，将尝试调整大小
     * @param concurrencyLevel 将同时写入映射的预期线程数
     * @param referenceType 用于条目的引用类型（SOFT或WEAK）
     */
    @SuppressWarnings("unchecked")
    public ConcurrentReferenceHashMap(
            int initialCapacity, float loadFactor, int concurrencyLevel, ReferenceType referenceType) {
        Assert.isTrue(initialCapacity >= 0, "Initial capacity must not be negative");
        Assert.isTrue(loadFactor > 0F, "Load factor must be positive");
        Assert.isTrue(concurrencyLevel > 0, "Concurrency must be positive");
        Assert.notNull(referenceType, "Reference must not be null");
        
        
        // 初始化 Segment 和 Entry
        this.loadFactor = loadFactor;
        this.shift = calculateShift(concurrencyLevel, MAXIMUM_CONCURRENCY_LEVEL);
        int size = 1 << this.shift;
        this.referenceType = referenceType;
        int roundedUpSegmentCapacity = (int) ((initialCapacity + size - 1L) / size);
        int initialSize = 1 << calculateShift(roundedUpSegmentCapacity, MAXIMUM_SEGMENT_SIZE);
        Segment[] segments = (Segment[]) Array.newInstance(Segment.class, size);
        int resizeThreshold = (int) (initialSize * getLoadFactor());
        for (int i = 0 ; i < segments.length ; i ++ ) {
            segments[i] = new Segment(initialSize, resizeThreshold);
        }
        this.segments = segments;
    }            
    
    
    /* METHODS */

    protected float getLoadFactor() {
        return loadFactor;
    }
    
    protected final int getSegmentSize() {
        return this.segments.length;
    }
    
    protected final Segment getSegment(int index) {
        return this.segments[index];
    }

    protected ReferenceManager createReferenceManager() {
        return new ReferenceManager();
    }

    /**
     * 获取给定对象的哈希值，应用额外的哈希函数来减少冲突。
     * 此实现使用与 {@link ConcurrentHashMap} 相同的 WangJenkins 算法
     * @param o 要散列的对象（可能为空）
     * @return 哈希码
     */
    protected int getHash(Object o) {
        int hash = (o != null ? o.hashCode() : 0);
        hash += (hash << 15) ^ 0xffffcd7d;
        hash ^= (hash >>> 10);
        hash += (hash << 3);
        hash ^= (hash >>> 6);
        hash += (hash << 2) + (hash << 14);
        hash ^= (hash >>> 16);
        return hash;
    }

    @Override
    public V get(Object key) {
        Reference<K, V> ref = getReference(key, Restructure.WHEN_NECESSARY);
        Entry<K, V> entry = ref != null ? ref.get() : null;
        return (entry != null ? entry.getValue() :  null);
    }
    
    @Override
    public V getOrDefault(Object key, V defaultValue) {
        Reference<K, V> ref = getReference(key, Restructure.WHEN_NECESSARY);
        Entry<K, V> entry = ref != null ? ref.get() : null;
        return (entry != null ? entry.getValue() : defaultValue);
    }

    @Override
    public boolean containsKey(Object key) {
        Reference<K, V> ref = getReference(key, Restructure.WHEN_NECESSARY);
        Entry<K, V> entry = ref != null ? ref.get() : null;
        return (entry != null && ObjectUtils.nullSafeEquals(entry.getKey(), key));
    }

    protected final Reference<K, V> getReference(Object key, Restructure restructure) {
        int hash = getHash(key);
        return getSegmentForHash(hash).getReference(key, hash, restructure);
    }

    @Override
    public V put(K key, V value) {
        return put(key, value, true);
    }
    
    @Override
    public V putIfAbsent(K key, V value) {
        return put(key, value, false);
    }
    
    private V put(K key, V value, final boolean overwritingExisting) {
        return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.RESIZE) {
            @Override
            protected V execute(Reference<K, V> ref, Entry<K, V> entry, Entries<V> entries) {
                if (entry != null) {
                    V oldValue = entry.getValue();
                    if (overwritingExisting) {
                        entry.setValue(value);
                    }
                    return oldValue;
                }
                Assert.state(entries != null, "No entries segment");
                entries.add(value);
                return null;
            }
        });
    }
    
    @Override
    public V remove(Object key) {
        return doTask(key, new Task<V>() {
            @Override
            protected V execute(Reference<K, V> ref, Entry<K, V> entry) {
                if (entry != null) {
                    if (ref != null) {
                        ref.release();
                    }
                    return entry.value;
                }
                return null;
            }
        });
    }
    
    @Override
    public boolean remove(Object key, Object value) {
        Boolean result = doTask(key, new Task<Boolean>(TaskOption.RESTRUCTURE_AFTER, TaskOption.SKIP_IF_EMPTY) {
            @Override
            protected Boolean execute(Reference<K, V> ref, Entry<K, V> entry) {
                if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), value)) {
                    if (ref != null) {
                        ref.release();
                    }
                    return true;
                }
                return false;
            }
        });
        return (Boolean.TRUE.equals(result));
    }
    
    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Boolean result = doTask(key, new Task<Boolean>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY) {
            @Override
            protected Boolean execute(Reference<K, V> ref, Entry<K, V> entry) {
                if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), oldValue)) {
                    entry.setValue(newValue);
                    return true;
                }
                return false;
            }
        });
        return (Boolean.TRUE.equals(result));
    }
    
    @Override
    public V replace(K key, V value) {
        return doTask(key, new Task<V>(TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY) {
            @Override
            protected V execute(Reference<K, V> ref, Entry<K, V> entry) {
                if (entry != null) {
                    V oldValue = entry.getValue();
                    entry.setValue(value);
                    return oldValue;
                }
                return null;
            }
        });
    }
    
    @Override
    public void clear() {
        for (Segment segment : this.segments) {
            segment.clear();
        }
    }

    /**
     * 删除任何已被垃圾收集且不再被引用的条目。
     * 在正常情况下，当在地图中添加或删除项目时，垃圾收集条目会自动清除。
     * 此方法可用于强制清除，当 Map 被频繁读取但更新频率较低时非常有用。
     */
    public void purgeUnreferencedEntries() {
        for (Segment segment : this.segments) {
            segment.restructureIfNecessary(false);
        }
    }

    @Override
    public int size() {
        int size = 0;
        for (Segment segment : this.segments) {
            size += segment.getCount();
        }
        return size;
    }
    
    @Override
    public boolean isEmpty() {
        for (Segment segment : this.segments) {
            if (segment.getCount() > 0) {
                return false;
            }
        }
        return true;
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> entrySet = this.entrySet;
        if (entrySet == null) {
            entrySet = new EntrySet();
            this.entrySet = entrySet;
        }
        return entrySet;
    }

    private <T> T doTask(Object key, Task<T> task) {
        int hash = getHash(key);
        return getSegmentForHash(hash).doTask(hash, key, task);
    }

    private Segment getSegmentForHash(int hash) {
        return this.segments[(hash >>> (32 - this.shift)) & (this.segments.length - 1)];
    }

    /**
     * 计算可用于在指定的最大值和最小值之间创建二次幂值的偏移值。
     * @param minimumValue 最小值
     * @param maximumValue 最大值
     * @return 计算出的偏移量（使用 {@code 1 << shift} 获取值）
     */
    protected static int calculateShift(int minimumValue, int maximumValue) {
        int shift = 0;
        int value = 1;
        while (value < minimumValue && value < maximumValue) {
            value <<= 1;
            shift++;
        }
        return shift;
    }
    
    /* INTERNAL INTERFACES OR CLASSES */
    
    /**
     * Various reference types supported by this map.
     */
    public enum ReferenceType {

        /** Use {@link SoftReference SoftReferences}. */
        SOFT,

        /** Use {@link WeakReference WeakReferences}. */
        WEAK
    }

    /**
     * 用于划分映射以允许更好的并发性能的单个段。
     */
    protected final class Segment extends ReentrantLock {
        
        private final ReferenceManager referenceManager;
        private final int initialSize;

        /**
         * 使用哈希中的低位索引的引用数组。
         * 此属性应仅与 {@code resizeThreshold} 一起设置。
         */
        private volatile Reference<K, V>[] references;

        /**
         * 此段中包含的引用总数。这包括链式引用和已被垃圾收集但未清除的引用。
         */
        private final AtomicInteger count = new AtomicInteger();

        /**
         * 调整大小的阈值。当 {@code count} 超过此值时，引用数组将被调整大小。
         */
        private int resizeThreshold;
        
        public Segment(int initialSize, int resizeThreshold) {
            this.referenceManager = createReferenceManager();
            this.initialSize = initialSize;
            this.references = createReferenceArray(initialSize);
            this.resizeThreshold = resizeThreshold;
        }
        
        public Reference<K, V> getReference(Object key, int hash, Restructure restructure) {
            if (restructure == Restructure.WHEN_NECESSARY) {
                restructureIfNecessary(false);
            }
            if (this.count.get() == 0) {
                return null;
            }
            // 使用本地副本来防止其他线程写入
            Reference<K, V>[] references = this.references;
            
            // Segment 第一次 hash 找到链表头 
            int index = getIndex(hash, references);
            Reference<K, V> head = references[index];
            
            // 在链表中寻找引用
            return findInChain(head, key, hash);
        }


        /**
         * 对该段应用更新操作。
         * 该段将在更新期间被锁定。
         * @param hash 键的哈希值
         * @param key 键
         * @param task 更新操作
         * @return 操作结果
         */
        public <T> T doTask(final int hash, final Object key, final Task<T> task) {
            boolean resize = task.hasOption(TaskOption.RESIZE);
            if (task.hasOption(TaskOption.RESTRUCTURE_BEFORE)) {
                restructureIfNecessary(resize);
            }
            if (task.hasOption(TaskOption.SKIP_IF_EMPTY) && this.count.get() == 0) {
                return task.execute(null, null, null);
            }
            lock();
            try {
                final int index = getIndex(hash, this.references);
                final Reference<K, V> head = this.references[index];
                Reference<K, V> ref = findInChain(head, key, hash);
                Entry<K, V> entry = ref != null ? ref.get() : null;
                Entries<V> entries = value -> {
                    Entry<K, V> newEntry = new Entry<>((K) key, value);
                    Reference<K, V> newReference = Segment.this.referenceManager.createReference(newEntry, hash, head);
                    Segment.this.references[index]  = newReference;
                    Segment.this.count.incrementAndGet();
                };
                return task.execute(ref, entry, entries);
            } finally {
                unlock();
                if (task.hasOption(TaskOption.RESTRUCTURE_AFTER)) {
                    restructureIfNecessary(resize);
                }
            }
        }

        /**
         * 清除该段中的所有项目。
         */
        public void clear() {
            if (this.count.get() == 0) {
                return;
            }
            lock();
            try {
                this.references = createReferenceArray(this.initialSize);   // 旧的 references 变为不可达状态，被 GC 清理
                this.resizeThreshold = (int) (this.references.length * getLoadFactor());    // 重新设置调整大小的阈值
                this.count.set(0);
            } finally {
                unlock();
            }
        }

        /**
         * 必要时重构底层数据结构。此方法可以增加引用表的大小并清除任何已被垃圾收集的引用。
         * @param allowResize 是否允许调整大小
         */
        protected final void restructureIfNecessary(boolean allowResize) {
            int currCount = this.count.get();
            boolean needsResize = allowResize && (currCount > 0 && currCount >= this.resizeThreshold);
            Reference<K, V> ref = this.referenceManager.pollForPurge();
            if (ref != null || (needsResize)) {
                restructure(allowResize, ref);
            }
        }
        
        private void restructure(boolean allowResize, Reference<K, V> ref) {
            boolean needsResize;
            lock();
            try {
                int countAfterRestructure = this.count.get();
                Set<Reference<K, V>> toPurge = Collections.emptySet();
                if (ref != null) {
                    toPurge = new HashSet<>();
                    while (ref != null) {
                        toPurge.add(ref);
                        ref = this.referenceManager.pollForPurge();
                    }
                }
                countAfterRestructure -= toPurge.size();
                
                // 重新计算考虑到锁内的计数和将被清除的项目
                needsResize = (countAfterRestructure > 0 && countAfterRestructure >= this.resizeThreshold);
                boolean resizing = false;
                int restructureSize = this.references.length;
                if (allowResize && needsResize && restructureSize < MAXIMUM_SEGMENT_SIZE) {
                    restructureSize <<= 1;
                    resizing = true;
                }
                
                // 创建一个新表或重用现有表
                Reference<K, V>[] restructured =
                        resizing ? createReferenceArray(restructureSize) : this.references;
                
                // 重组
                for (int i = 0 ; i < this.references.length ; i ++ ) {
                    ref = this.references[i];
                    if (! resizing) {
                        restructured[i] = null;
                    }
                    while (ref != null) {
                        if (! toPurge.contains(ref)) {
                            Entry<K, V> entry = ref.get();
                            if (entry != null) {
                                int index = getIndex(ref.getHash(), restructured);
                                restructured[index] = this.referenceManager.createReference(
                                        entry, ref.getHash(), restructured[index]);
                            }
                        }
                        ref = ref.getNext();
                    }
                }
                
                // 替换 volatile 成员
                if (resizing) {
                    this.references = restructured;
                    this.resizeThreshold = (int) (this.references.length * getLoadFactor());
                }
                this.count.set(Math.max(countAfterRestructure, 0));
                
            } finally {
                unlock();
            }
        }

        private Reference<K, V> findInChain(Reference<K, V> ref, Object key, int hash) {
            Reference<K, V> currRef = ref;
            while (currRef != null) {
                if (currRef.getHash() == hash) {
                    Entry<K, V> entry = currRef.get();
                    if (entry != null) {
                        K entryKey = entry.getKey();
                        if (ObjectUtils.nullSafeEquals(entryKey, key)) {
                            return currRef;
                        }
                    }
                }
                currRef = currRef.getNext();
            }
            return null;
        }

        @SuppressWarnings({"rawtypes", "unchecked"})
        private Reference<K, V>[] createReferenceArray(int size) {
            return new Reference[size];
        }

        private int getIndex(int hash, Reference<K, V>[] references) {
            return (hash & (references.length - 1));
        }

        /**
         * 返回当前引用数组的大小。
         */
        public final int getSize() {
            return this.references.length;
        }

        /**
         * 返回此段中的引用总数。
         */
        public final int getCount() {
            return this.count.get();
        }
    }
    
    protected interface Reference<K, V> {

        /**
         * 返回引用的条目，如果该条目不再可用，则返回 {@code null}。
         */
        Entry<K, V> get();

        /**
         * 返回引用的哈希值
         */
        int getHash();

        /**
         * 返回链中的下一个引用，如果没有则返回 {@code null}。
         */
        Reference<K, V> getNext();

        /**
         * 释放此条目并确保它将从 {@code ReferenceManager#pollForPurge()} 返回。
         */
        void release();
    }

    /**
     * 单个映射条目
     * @param <K> 键类型
     * @param <V> 值类型
     */
    protected static final class Entry<K, V> implements Map.Entry<K, V> {
        
        private final K key;
        
        private volatile V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public K getKey() {
            return this.key;
        }

        @Override
        public V getValue() {
            return this.value;
        }

        @Override
        public V setValue(V value) {
            V previous = this.value;
            this.value = value;
            return previous;
        }

        @Override
        public String toString() {
            return (this.key + "=" + this.value);
        }
    }

    /**
     * 可以针对 {@link Segment} {@link Segment#doTask run} 的任务。
     */
    private abstract class Task<T> {
        
        private final EnumSet<TaskOption> options;
        
        public Task(TaskOption... options) {
            this.options = (options.length == 0 ? EnumSet.noneOf(TaskOption.class) : EnumSet.of(options[0], options));
        }
        
        public boolean hasOption(TaskOption option) {
            return this.options.contains(option);
        }

        /**
         * 执行任务。
         * @param ref 找到的引用（或 {@code null}）
         * @param entry 找到的条目（或 {@code null}）
         * @param entries 访问底层条目
         * @return 任务的结果
         * @see #execute(Reference, Entry) 
         */
        protected T execute(Reference<K, V> ref, Entry<K, V> entry, Entries<V> entries) {
            return execute(ref, entry);
        }

        /**
         * 可用于不需要访问 {@link Entries} 的任务的便捷方法。
         * @param ref 找到的引用（或 {@code null}）
         * @param entry 找到的条目（或 {@code null}）
         * @return 任务的结果
         * @see #execute(Reference, Entry, Entries)
         */
        protected T execute(Reference<K, V> ref, Entry<K, V> entry) {
            return null;
        }
        
    }

    /**
     * {@code Task} 支持的各种选项
     */
    private enum TaskOption {
        RESTRUCTURE_BEFORE, RESTRUCTURE_AFTER, SKIP_IF_EMPTY, RESIZE
    }

    /**
     * 允许任务访问 {@link ConcurrentReferenceHashMap.Segment} 条目。
     */
    private interface Entries<V> {
        /**
         * 添加具有指定值的新条目。
         * @param value 要添加的值
         */
        void add(V value);
    }

    /**
     * 内部条目集合实现。
     */
    private class EntrySet extends AbstractSet<Map.Entry<K, V>> {

        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return new EntryIterator();
        }

        @Override
        public boolean contains(Object o) {
            if (o instanceof Map.Entry<?, ?>) {
                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
                Reference<K, V> ref = ConcurrentReferenceHashMap.this.getReference(entry.getKey(), Restructure.NEVER);
                Entry<K, V> otherEntry = ref != null ? ref.get() : null;
                if (otherEntry != null) {
                    return ObjectUtils.nullSafeEquals(entry.getValue(), otherEntry.getValue());
                }
            }
            return false;
        }

        @Override
        public boolean remove(Object o) {
            if (o instanceof Map.Entry<?, ?>) {
                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
                return ConcurrentReferenceHashMap.this.remove(entry.getKey(), entry.getValue());
            }
            return false;
        }

        @Override
        public int size() {
            return ConcurrentReferenceHashMap.this.size();
        }

        @Override
        public void clear() {
            ConcurrentReferenceHashMap.this.clear();
        }
    }

    /**
     * todo 内部条目迭代器实现
     */
    private class EntryIterator implements Iterator<Map.Entry<K, V>> {
       
        private int segmentIndex;
        
        private int referenceIndex;
    
        private Reference<K, V>[] references;
        
        private Reference<K, V> reference;

        private Entry<K, V> next;
        
        private Entry<K, V> last;

        public EntryIterator() {
            moveToNextSegment();
        }
        
        @Override
        public boolean hasNext() {
            getNextIfNecessary();
            return (this.next != null);
        }

        @Override
        public Entry<K, V> next() {
            getNextIfNecessary();
            if (this.next == null) {
                throw new NoSuchElementException();
            }
            this.last = this.next;
            this.next = null;
            return this.last;
        }
        
        private void getNextIfNecessary() {
            while (this.next == null) {
                moveToNextReference();
                if (this.reference == null) {
                    return;
                }
                this.next = this.reference.get();
            }
        }

        private void moveToNextReference() {
            if (this.reference != null) {
                this.reference = this.reference.getNext();
            }
            while (this.reference == null && this.references != null) {
                // references 链表越界，跳转到下一个 Segment
                if (this.referenceIndex >= this.references.length) {
                    moveToNextSegment();
                    this.referenceIndex = 0;
                }
                else {
                    this.reference = this.references[this.referenceIndex];
                    this.referenceIndex ++;
                }
            }
        }
        
        private void moveToNextSegment() {
            this.reference = null;
            this.references = null;
            if (this.segmentIndex < ConcurrentReferenceHashMap.this.segments.length) {
                this.references = ConcurrentReferenceHashMap.this.segments[this.segmentIndex].references;
                this.segmentIndex ++;
            }
        }
        
        @Override
        public void remove() {
            Assert.state(this.last != null, "No element to remove");
            ConcurrentReferenceHashMap.this.remove(this.last.getKey());
            this.last = null;
        }
    }

    /**
     * 可以执行的重组类型
     */
    protected enum Restructure {
        WHEN_NECESSARY, NEVER
    }

    /**
     * 用于管理 {@link Reference References} 的策略类。如果需要支持替代引用类型，则可以覆盖此类
     */
    protected class ReferenceManager {
        
        private final ReferenceQueue<Entry<K, V>> queue = new ReferenceQueue<>();

        /**
         * 用于创建新的 {@link Reference} 的工厂方法。
         * @param entry 引用中包含的条目
         * @param hash 哈希值
         * @param next 链中的下一个引用，如果没有则为 {@code null}
         * @return 一个新的{@link Reference}
         */
        public Reference<K, V> createReference(Entry<K, V> entry, int hash, Reference<K, V> next) {
            if (ConcurrentReferenceHashMap.this.referenceType == ReferenceType.WEAK) {
                return new WeakEntryReference<>(entry, hash, next, this.queue);
            }
            return new SoftEntryReference<>(entry, hash, next, this.queue);
        }

        /**
         * 返回任何已被垃圾收集并可以从底层结构中清除的引用，如果没有引用需要清除，则返回 {@code null}。
         * 此方法必须是线程安全的，理想情况下不应在返回 {@code null} 时阻塞。引用应返回一次且仅一次。
         * @return 对清除或 {@code null} 的引用
         */
        @SuppressWarnings("unchecked")
        public Reference<K, V> pollForPurge() {
            return (Reference<K, V>) this.queue.poll();
        }
        
    }
    
    /**
     * {@link SoftReference SoftReferences} 的内部{@link Reference} 实现
     * 软引用：内存不足时被 gc
     */
    private class SoftEntryReference<K, V> extends SoftReference<Entry<K, V>> implements Reference<K, V> {
        
        private final int hash;

        private final Reference<K, V> nextReference;


        private SoftEntryReference(Entry<K, V> entry, int hash, Reference<K, V> next,
                                   ReferenceQueue<Entry<K, V>> queue) {
            super(entry, queue);
            this.hash = hash;
            this.nextReference = next;
        }

        @Override
        public int getHash() {
            return this.hash;
        }

        @Override
        public Reference<K, V> getNext() {
            return this.nextReference;
        }

        @Override
        public void release() {
            enqueue();
            clear();
        }
    }
    
    /**
     * {@link WeakReference WeakReferences} 的内部{@link Reference} 实现
     * 弱引用：一旦GC，就被回收
     */
    private class WeakEntryReference<K, V> extends WeakReference<Entry<K, V>> implements Reference<K, V> {
        
        private final int hash;
        
        private final Reference<K, V> nextReference;
        
        private WeakEntryReference(Entry<K, V> entry, int hash, Reference<K, V> next,
                                   ReferenceQueue<Entry<K, V>> queue) {
            super(entry, queue);
            this.hash = hash;
            this.nextReference = next;
        }

        @Override
        public int getHash() {
            return this.hash;
        }
        
        @Override
        public Reference<K, V> getNext() {
            return this.nextReference;
        }

        @Override
        public void release() {
            enqueue();
            clear();
        }
    }
    
    
}
